﻿namespace Zipper

module Zipper =

    /// An abstract breadcrumb for a recursive datastructure.
    type 'a breadcrumb =
        abstract member Reconstruct: 'a -> 'a

    /// A zipper for a recursive datastructure.
    type 'a zipper = Zipper of 'a * 'a breadcrumb list

    /// Tries to move the zipper upwards.
    let tryUp (Zipper (x, cs)) =
        match cs with
            | [] -> None
            | (c::cs') -> (c.Reconstruct(x), cs') |> Zipper |> Some

    /// Moves the zipper upwards.
    let up z = (tryUp z).Value

    /// Gets the focus of the specified zipper.
    let focus (Zipper (x, _)) = x

    /// Move the zipper all the way to the top.
    let rec top z =
        match tryUp z with
            | None -> z
            | Some z' -> top z'

    /// Reconstructs the datum from its zipper.
    let zip z = z |> top |> focus

    /// Tries to move downwards.
    let tryDown move (Zipper (x, cs)) =
        match move x with
            | Some (x', c) -> Zipper (x', c::cs) |> Some
            | None -> None

    /// Moves downwards.
    let down move z = (tryDown move z).Value

    /// Creates a zipper for the specified datum.
    let unzip x = Zipper (x, [])

    /// Modifies the focused datum of the specified zipper.
    let modify f (Zipper (x, cs)) = Zipper (f x, cs)